Chapter 1

The way of the program

based on How to Think Like a Computer Scientist: Python Version :Chapter 1

The goal of this class is to teach you to think like a computer scientist.

This way of thinking combines some of the best features of:

Mathematics
- uses formal languages to denote ideas (specifically computations)
Engineering
- design things
- assemble components into systems
- evaluate tradeoffs among alternatives
Natural Science
- observe behavior of complex systems
- form hypotheses
- test predictions

The single most important skill for a computer scientist is problem solving:

formulate problems
think creatively about solutions
express a solution clearly and accurately

Learning to program is about learning to solve problems.

1.1 The Python programming language

Two types of programming languages:

High-level
- Python
- C
- C++
- Perl
- Java
Low-level (assembly or machine languages) - Computer specific
- Intel x86 (Pentium) - IBM PC compatibles
- Motorola/IBM PowerPC - Apple Macintosh; IBM workstations and servers
- Sun SPARC - Sun workstations and servers

Computers only execute low level languages. Programs written in high level languages are translated to the machine language of the specific computer.

Advantage of low-level programming language: program can be tuned to specific computer for maximum execution speed and minimum memory consumption.

Advantages of high-level programming languages:

easier to program
- less time to write
- shorter and easier to read
- more likely to be correct (fewer bugs)
much easier to port, or modify to run on different computers

Today almost all programs are written in high-level programming languages.

Two types of programs translate high-level languages to machine language: interpreters and compilers.

interpreter
Reads high-level program and executes it. Alternates between reading lines of program and executing or carrying out commands.

image from How to Think Like a Computer Scientist: Python Version
compiler
Reads high-level program and translates it all at once, before executing any of the commands. Compilation is often a separate step. The high-level program is called source code, and the translated program is called the object code or the executable.

image from How to Think Like a Computer Scientist: Python Version

Python is considered an interpreted language because Python programs are executed by an interpreter.

The interpreter can be run in command-line mode or script mode:

command-line mode

You type Python statements, and the interpreter prints the result.

  $ python
  Python 1.5.2 (#1, Feb  1 2000, 16:32:16)
  Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
  >>> print 1 + 1
  2

script mode
Write a text file, also called a script, and tell the interpreter to execute it.
We create a file named latoya.py with the following contents:
```
  print 1 + 1
	
```
By convention, files that contain Python programs have names that end with .py.
To execute the program, you have to tell the interpreter the name of the script.
```
  $ python latoya.py
  2
	
```
The command line is useful for testing simple statements. Finished programs are normally stored and run as scripts. Both techniques are supported by IDLE, the Python Integrated Development Environment we will be learning about in homework 1.

1.2 What is a program?

A program is a sequence of instructions that specifies how to perform a computation.

Examples:

mathematical
- solving a system of equations
- finding the roots of a polynomial
symbolic computation
- searching and replacing text in a document
- interpreting a program (like the Python interpreter!)

Instructions (or commands, or statements) look different in different programming languages, but a few basic instructions appear in almost every language:

input
- Get data from the keyboard, or a file, or some other device.
output
- Display data on the screen or send data to a file or other device.
math
- Perform basic mathematical operations like addition and multiplication.
conditional execution
- Check for certain conditions and execute the appropriate sequence of statements.
repetition
- Perform some action repeatedly, usually with some variation.

All programs consist of instructions like these. So one way to describe programming is the process of breaking a large, complex task up into smaller and smaller subtasks until eventually the subtasks are simple enough to be performed with one of these simple instructions.

We will come back to this topic later when we discuss algorithms.

1.3 What is debugging?

Programming errors are called bugs. The process of tracking them down and correcting them is called debugging.

There are three kinds of program errors:

1.3.1 Syntax errors

Python cannot execute a program unless it is syntactically correct. Otherwise it returns an error message without starting the program. Syntax refers to the structure of your program and rules about that structure.

In English, a sentence must begin with a capital letter and end with a period.

this sentence contains a syntax error.
So does this one

A Python example is mismatched parenthesis:

      (5/2))
           ^
  SyntaxError: invalid syntax

1.3.2 Run-time errors

Do not occur until the program is run and the particular faulty line is executed.
Called exceptions because something exceptional (and usually bad) has happened.
Execution of your program is normally terminated at this point.
Information about the current state of the program is printed.

An example is a division-by-zero error:

   >>> 5/0
   Traceback (innermost last):
     File "<pyshell#9>", line 1, in ?
       5/0
   ZeroDivisionError: integer division or modulo

1.3.3 Logic or semantic errors

In this case the program runs successfully, in the sense that it does not generate any error messages, but it doesn't do what you want it to do. Instead it is doing what you told it to do!

Debugging logical errors requires you to work backwards from the observed output (if any) to determine what the program is actually doing internally.

1.4 Experimental Debugging

One of the most important skills you will acquire in this class is debugging.

Some programmers (such as the authors of How to Think Like a Computer Scientist) believe debugging is one of the most intellectually rich, challenging, and interesting parts of programming.

Debugging is like detective work:

You are confronted with clues, and you have to infer the processes and events that lead to the results you see.

Debugging is also like an experimental science:

Form hypothesis about cause of error.
Modify program, and predict new outcome.
If results match prediction, hypothesis is correct.
Otherwise, modify hypothesis.

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth" (Sherlock Holmes, from A. Conan Doyle's The Sign of Four)

For some people, programming and debugging are the same thing:

Programming is the process of debugging a program until it does what you want.
- Start with a working program that does something.
- Make small modifications, debugging them as you go.
- Always have a working program.
Example of this style of development: Linux
- Linus Torvalds started out writing a program to explore the Intel 80386 chip.
- It simply switched between printing AAAA and BBBB.
- Evolved to Linux!

1.5 Formal and natural languages

Natural Languages

Languages people speak, like English, Spanish and French.
Not designed by people; they evolved naturally.

Formal Languages are designed for specific applications:

mathematicians
- mathematical notation is a formal language for denoting relationships between numbers and symbols
chemists
- chemical notation is a formal language to represent chemical structure of molecules
computer scientists
- programming languages are formal languages that have been designed to express computations

Formal languages tend to have strict rules about syntax.

3+3=6 is a syntactically correct mathematical statement
3=+6$ is not
H₂O is a syntactically correct chemical name
₂Zz is not

Two types of syntax rules:

Token rules
- tokens are basic elements of the language
  - words
  - numbers
  - chemical elements
- in 3=+6$, $ is not a legal token in mathematics
- in ₂Zz, there is no element with abbreviation Zz
Structure rules
- the way tokens are arranged in a statement
- in 3=+6, plus is not allowed to follow equals
- in ₂Zz, subscripts must come after the element name, not before

The process of determining the structure of a sentence in a natural or formal language is called parsing.

Example: "The other shoe fell"
- "the other shoe" is the subject
- "fell" is the verb

After parsing a sentence you can determine the meaning or semantics of the sentence.

Formal and natural languages share:

tokens
structure
syntax
semantics

Formal and natural languages differ on:

ambiguity
- Natural languages are full of ambiguity. People use contextual clues and other information.
- Formal languages are designed to be unambiguous. Each statement has exactly one meaning.
redundancy
- Natural languages are redundant to make up for ambiguity and reduce miscommunications.
- Natural languages are verbose.
- Formal languages are less redundant and more concise.
literalness
- Natural languages are full of idiom and metaphor: no shoe, no falling.
- Formal languages mean exactly what they say.

The difference between formal and natural languages has been compared to the difference between prose and poetry.

1.6 The first program

Traditionally the first program people write in a new language is called "Hello, World!" because all it does is print the words "Hello, World!" In Python, this program looks like this:

  print "Hello, World!"